{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Palindromic Substring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestPalindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长回文子串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code>，找到 <code>s</code> 中最长的回文子串。</p>\n",
    "\n",
    "<p>如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"babad\"\n",
    "<strong>输出：</strong>\"bab\"\n",
    "<strong>解释：</strong>\"aba\" 同样是符合题意的答案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"cbbd\"\n",
    "<strong>输出：</strong>\"bb\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 1000</code></li>\n",
    "\t<li><code>s</code> 仅由数字和英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-palindromic-substring](https://leetcode.cn/problems/longest-palindromic-substring/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-palindromic-substring](https://leetcode.cn/problems/longest-palindromic-substring/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"babad\"', '\"cbbd\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        dp = [[False]*n for _ in range(n)]\n",
    "        ans = [-1,-1]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = True\n",
    "            ans = [i,i]\n",
    "        for i in range(n-1):\n",
    "            if s[i] == s[i+1]:\n",
    "                dp[i][i+1] = True\n",
    "                ans = [i, i+1]\n",
    "        for diff in range(2, n):\n",
    "            for i in range(n-diff):\n",
    "                j = i + diff\n",
    "                if s[i] == s[j] and dp[i+1][j-1]:\n",
    "                    dp[i][j] = True\n",
    "                    ans = [i,j]\n",
    "        return s[ans[0]:ans[1]+1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s):\n",
    "        length = len(s)\n",
    "        start, end, Max_len = 0, 0, 1\n",
    "        for i in range(length):\n",
    "            p, q = i-1, i+1\n",
    "            len_temp = 1\n",
    "            while p >= 0 and q < length and s[p] == s[q]:\n",
    "                p -= 1\n",
    "                q += 1\n",
    "                len_temp += 2\n",
    "            if len_temp > Max_len:\n",
    "                Max_len = len_temp\n",
    "                start, end = p+1, q-1\n",
    "\n",
    "            p, q = i, i+1\n",
    "            len_temp = 0\n",
    "            while p >= 0 and q < length and s[p] == s[q]:\n",
    "                p -= 1\n",
    "                q += 1\n",
    "                len_temp += 2\n",
    "            if len_temp > Max_len:\n",
    "                Max_len = len_temp\n",
    "                start, end = p+1, q-1\n",
    "        return s[start:end+1]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self,s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        对于每个位置i：\n",
    "            d = 0\n",
    "            currentleft = i - 1\n",
    "            currentright = i + 1\n",
    "            while currentleft 存在 且 currentright 存在 且s[currentleft] == s[currentright]:\n",
    "                d += 1\n",
    "                currentleft -= 1\n",
    "                currentright += 1\n",
    "            L[i] = d\n",
    "        \"\"\"\n",
    "\n",
    "        position_lps = []\n",
    "        s = '|'+'|'.join(s)+'|'\n",
    "        L = {}\n",
    "        max_length = 0\n",
    "        longest = 0 \n",
    "        for i in range(len(s)):\n",
    "            d = 0\n",
    "            currentleft = i - 1\n",
    "            currentright = i + 1\n",
    "            while currentleft >= 0 and currentright < len(s) and s[currentleft] == s[currentright]:\n",
    "                d += 1\n",
    "                currentleft -= 1\n",
    "                currentright += 1\n",
    "            L[i] = d \n",
    "            if d > max_length:\n",
    "                longest = i \n",
    "                max_length = d\n",
    "        longestP = s[longest - L[longest]:longest] + s[longest:longest+L[longest]+1]\n",
    "        return longestP.replace('|','')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        str_len=len(s)\n",
    "        self.max_len=1\n",
    "        self.start_index=0\n",
    "        if len(s)<2:\n",
    "            return s\n",
    "        for i in range(str_len):\n",
    "            self.tuozhan(s,i,i)\n",
    "            self.tuozhan(s,i,i+1)\n",
    "        return s[self.start_index:self.start_index+self.max_len]\n",
    "    def tuozhan(self,s,left,right):\n",
    "        #考虑限制边界和条件\n",
    "        while left>=0 and right<len(s) and s[left]==s[right]:\n",
    "            left-=1\n",
    "            right+=1\n",
    "        #更新长度和位置\n",
    "        if right -left-1>self.max_len:\n",
    "            self.max_len=right-left-1\n",
    "            self.start_index=left+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        #全局变量\n",
    "        re = ''\n",
    "        mi = ''\n",
    "        if len(s) == 1:#单字符\n",
    "            re = s\n",
    "        elif len(s) == 2:#双字符\n",
    "            if s[0] == s[1]:\n",
    "                re = s\n",
    "            else:\n",
    "                re =s[0]\n",
    "        else:\n",
    "            print('奇循环')\n",
    "            for i in range(len(s)-2):#奇回文搜索\n",
    "                p = i+1\n",
    "                if p >= len(s)/2:\n",
    "                    r = len(s) - p - 1\n",
    "                else:\n",
    "                    r = p\n",
    "                #print('p = '+str(p))\n",
    "                #print('r = '+str(r))\n",
    "                for j in range(r):\n",
    "                    j2 = j + 1\n",
    "                    if s[p-j2] != s[p+j2]:\n",
    "                        mi = s[p-j2+1:p+j2]\n",
    "                        #print('mi = '+mi)\n",
    "                        if len(mi) > len(re):\n",
    "                            re = mi\n",
    "                        break\n",
    "                    if j2 == r:\n",
    "                        mi = s[p-j2:p+j2+1]\n",
    "                        #print('mi = '+mi)\n",
    "                        if len(mi) > len(re):\n",
    "                            re = mi\n",
    "            print('偶循环')\n",
    "            for i in range(len(s)-1):\n",
    "                p = i+1\n",
    "                if p >= len(s)/2:\n",
    "                    r = len(s) - p\n",
    "                else:\n",
    "                    r = p\n",
    "                #print('p = '+str(p))\n",
    "                #print('r = '+str(r))\n",
    "                for j in range(r):\n",
    "                    j2 = j + 1\n",
    "                    if s[p-j2] != s[p+j2-1]:\n",
    "                        mi = s[p-j2+1:p+j2-1]\n",
    "                        #print('mi = '+mi)\n",
    "                        if len(mi) > len(re):\n",
    "                            re = mi\n",
    "                        break\n",
    "                    if j2 == r:\n",
    "                        mi = s[p-j2:p+j2]\n",
    "                        #print('mi = '+mi)\n",
    "                        if len(mi) > len(re):\n",
    "                            re = mi\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def longestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if len(s) <= 1:\n",
    "            return s\n",
    "        lognest = s[0:1]\n",
    "        for i in range(0, len(s)):\n",
    "            tmp = self.str_helper(s, i, i)\n",
    "            if len(tmp) > len(lognest):\n",
    "                lognest = tmp\n",
    "            tmp = self.str_helper(s, i, i + 1)\n",
    "            if len(tmp) > len(lognest):\n",
    "                lognest = tmp\n",
    "        return lognest\n",
    "\n",
    "    def str_helper(self, s1, left, right):\n",
    "        n = len(s1)\n",
    "        while left >= 0 and right <= n - 1 and s1[left] == s1[right]:\n",
    "            left -= 1\n",
    "            right += 1\n",
    "        return s1[left + 1:right]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: 'str') -> 'str':\n",
    "        if s!=\"\":\n",
    "            self.s = s\n",
    "            ls,rs,les = zip(*[self.l_eq_r(i-1,i+1) for i in range(len(s))] + [self.l_eq_r(i,i+1) for i in range(len(s))])\n",
    "            max_pos = les.index(max(les))\n",
    "            return self.s[ls[max_pos]:rs[max_pos]]\n",
    "        else:\n",
    "            return \"\"\n",
    "    def l_eq_r(self, l, r):\n",
    "        if l>=0 and r<=len(self.s)-1:\n",
    "            if self.s[l] == self.s[r]:\n",
    "                return self.l_eq_r(l-1, r+1)\n",
    "        return l+1, r, r-l-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        str_len = len(s)\n",
    "        if str_len == 1:\n",
    "            return s\n",
    "        odd = [[n, n] for n in range(str_len)]\n",
    "        even = [[n, n+1] for n in range(str_len-1) if s[n]==s[n+1]]\n",
    "\n",
    "        while True:\n",
    "            new_odd = []\n",
    "            new_even = []\n",
    "            for n in range(len(odd)):\n",
    "                i = odd[n][0]\n",
    "                j = odd[n][1]\n",
    "                if i > 0 and j < str_len - 1 and s[i-1] == s[j+1]:\n",
    "                    new_odd.append([i-1, j+1])\n",
    "\n",
    "            for n in range(len(even)):\n",
    "                i = even[n][0]\n",
    "                j = even[n][1]\n",
    "                if i > 0 and j < str_len - 1 and s[i-1] == s[j+1]:\n",
    "                    new_even.append([i-1, j+1])\n",
    "\n",
    "            if new_odd or new_even:\n",
    "                odd = new_odd\n",
    "                even = new_even\n",
    "            else:\n",
    "                max_len = 0\n",
    "                l_str = ''\n",
    "                for item in odd:\n",
    "                    i = item[0]\n",
    "                    j = item[1]\n",
    "                    if j - i + 1 > max_len:\n",
    "                        max_len = j - i + 1\n",
    "                        l_str = s[i:j+1]\n",
    "                for item in even:\n",
    "                    i = item[0]\n",
    "                    j = item[1]\n",
    "                    if j - i + 1 > max_len:\n",
    "                        max_len = j - i + 1\n",
    "                        l_str = s[i:j + 1]\n",
    "                return l_str\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: 'str') -> 'str':\n",
    "        start = 0\n",
    "        end = 0\n",
    "        for i in range(len(s)):\n",
    "            len_str1 = self.expendsAroundCenter(s, i, i)\n",
    "            len_str2 = self.expendsAroundCenter(s, i, i + 1)\n",
    "            print(len_str1, len_str2)\n",
    "            max_len = max(len_str1, len_str2)\n",
    "            if max_len > end - start:\n",
    "                start = i - (max_len - 1) // 2\n",
    "                end = i + max_len // 2\n",
    "        return s[start:end + 1]\n",
    "\n",
    "    def expendsAroundCenter(self, s: 'str', left: 'int',\n",
    "                            right: 'int') -> 'str':\n",
    "        while (left >= 0 and right < len(s) and s[left] == s[right]):\n",
    "            left -= 1\n",
    "            right += 1\n",
    "        return right - left - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        str_len = len(s)\n",
    "        if str_len == 1:\n",
    "            return s\n",
    "        odd = [[n, n] for n in range(str_len)]\n",
    "        even = [[n, n+1] for n in range(str_len-1) if s[n]==s[n+1]]\n",
    "\n",
    "        while True:\n",
    "            new_odd = []\n",
    "            new_even = []\n",
    "            for n in range(len(odd)):\n",
    "                i = odd[n][0]\n",
    "                j = odd[n][1]\n",
    "                if i > 0 and j < str_len - 1 and s[i-1] == s[j+1]:\n",
    "                    new_odd.append([i-1, j+1])\n",
    "\n",
    "            for n in range(len(even)):\n",
    "                i = even[n][0]\n",
    "                j = even[n][1]\n",
    "                if i > 0 and j < str_len - 1 and s[i-1] == s[j+1]:\n",
    "                    new_even.append([i-1, j+1])\n",
    "\n",
    "            if new_odd or new_even:\n",
    "                odd = new_odd\n",
    "                even = new_even\n",
    "            else:\n",
    "                max_len = 0\n",
    "                l_str = ''\n",
    "                for item in odd:\n",
    "                    i = item[0]\n",
    "                    j = item[1]\n",
    "                    if j - i + 1 > max_len:\n",
    "                        max_len = j - i + 1\n",
    "                        l_str = s[i:j+1]\n",
    "                for item in even:\n",
    "                    i = item[0]\n",
    "                    j = item[1]\n",
    "                    if j - i + 1 > max_len:\n",
    "                        max_len = j - i + 1\n",
    "                        l_str = s[i:j + 1]\n",
    "                return l_str\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if(len(s)==1):\n",
    "            return s\n",
    "        dict_string = {}\n",
    "        for i in range(len(s)):\n",
    "            l = i - 1\n",
    "            if l < 0:\n",
    "                l = 0\n",
    "            r = i + 1\n",
    "            if r >= len(s):\n",
    "                r = len(s)\n",
    "            while l >= 0 and r < len(s) and s[l] == s[r]:\n",
    "                l = l - 1\n",
    "                r = r + 1\n",
    "            l = l + 1\n",
    "            if s[l:r] not in dict_string:\n",
    "                dict_string[s[l:r]] = r - l\n",
    "        for j in range(len(s)):\n",
    "            n_l = j\n",
    "            n_r = j + 1\n",
    "            while n_l >= 0 and n_r < len(s) and s[n_l] == s[n_r]:\n",
    "                n_l = n_l - 1\n",
    "                n_r = n_r + 1\n",
    "            n_l = n_l + 1\n",
    "            if s[n_l:n_r] not in dict_string:\n",
    "                dict_string[s[n_l:n_r]] = n_r - n_l\n",
    "\n",
    "        max_str = 0\n",
    "        return_info = ''\n",
    "        for dd in dict_string:\n",
    "            if dict_string[dd] >= max_str:\n",
    "                max_str = dict_string[dd]\n",
    "                return_info = dd\n",
    "\n",
    "        return return_info\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        record={}\n",
    "        end=len(s)\n",
    "        if end==0:\n",
    "            return s\n",
    "        for i in range(2,end+1):\n",
    "            n=0\n",
    "            while n+i<=end:\n",
    "                temp=s[n:n+i]\n",
    "                temp_reverse=temp[::-1]\n",
    "                n+=1\n",
    "                if temp==temp_reverse:\n",
    "                    record[i]=temp\n",
    "                    break;\n",
    "        if not record:\n",
    "            return s[0]\n",
    "        else:\n",
    "            value=max(record.keys())\n",
    "            return record[value]\n",
    "                    \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, str1):\n",
    "        \"\"\"\n",
    "        :type strings: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if len(str1)<2:\n",
    "            return str1\n",
    "        str2 = str1[::-1]\n",
    "        currList = [0]*len(str2)\n",
    "        strDict = {}\n",
    "        len1, len2 = len(str1), len(str2)\n",
    "        for i, s2 in enumerate(str2):\n",
    "            if s2==str1[0]:\n",
    "                currList[i]=1\n",
    "        for r, s1 in enumerate(str1[1:]):\n",
    "            # 每一行开头更新List\n",
    "            oldList = currList.copy()\n",
    "            #pdb.set_trace()\n",
    "            for i, s2 in enumerate(str2):\n",
    "                if s2==s1:\n",
    "                    if r==len1-2 and i==len2-1 and s1==s2:\n",
    "                        # 边缘情况：处理矩阵右下角元素：对角更新规则导致右下角上面的元素无法处理\n",
    "                        if oldList[i]>1:\n",
    "                            len_common=oldList[i]\n",
    "                            strDict[len_common] = str2[i+1-len_common:i+1]\n",
    "                    # 边缘情况：处理矩阵每行第一个元素：直接更新currList[i]为1\n",
    "                    if i==0:\n",
    "                        currList[i]=1\n",
    "                    else:\n",
    "                        currList[i]=oldList[max(0,i-1)]+1\n",
    "\n",
    "\n",
    "                else:\n",
    "                    # 策略：只有s2!=s1且上一行左上值大于1时（即对角线断了）的场景才保存一次strDict\n",
    "                    # 但是这样无法处理最后一个值s1==s2的情况，因为该情况不更新strDict。故需要在最后一行一列的位置额外处理currList。\n",
    "                    currList[i]=0\n",
    "                    if i>1 and oldList[i-1]>1:\n",
    "                        len_common = oldList[i-1]\n",
    "                        strDict[len_common] = str2[i-len_common:i]\n",
    "\n",
    "                        # 边缘情况： 处理每行最后一个元素\n",
    "                    if i==len2-1 and oldList[i]>1:\n",
    "                        len_common = oldList[i]\n",
    "                        strDict[len_common] = str2[i-len_common+1:]\n",
    "                # 边缘情况：处理矩阵最后一行: 直接用currList，不再使用oldList判断是否停止\n",
    "                if r == len1-2:\n",
    "                    #pdb.set_trace()\n",
    "                    if currList[i]>1:\n",
    "                        len_common = currList[i]\n",
    "                        strDict[len_common] = str2[i+1-len_common:i+1]\n",
    "        strDict = {k:v for k,v in strDict.items() if v==v[::-1]}\n",
    "        if len(strDict)==0:\n",
    "            return str1[0]\n",
    "        else:\n",
    "            return strDict[max(strDict.keys())]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, str1):\n",
    "        \"\"\"\n",
    "        :type strings: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if len(str1)<2:\n",
    "            return str1\n",
    "        str2 = str1[::-1]\n",
    "        currList = [0]*len(str2)\n",
    "        strDict = {}\n",
    "        len1, len2 = len(str1), len(str2)\n",
    "        for i, s2 in enumerate(str2):\n",
    "            if s2==str1[0]:\n",
    "                currList[i]=1\n",
    "        for r, s1 in enumerate(str1[1:]):\n",
    "            # 每一行开头更新List\n",
    "            oldList = currList\n",
    "            currList = [0]*len(str2)  #### 更新！！\n",
    "            #pdb.set_trace()\n",
    "            for i, s2 in enumerate(str2):\n",
    "                if s2==s1:\n",
    "                    if r==len1-2 and i==len2-1 and s1==s2:\n",
    "                        # 边缘情况：处理矩阵右下角元素：对角更新规则导致右下角上面的元素无法处理\n",
    "                        if oldList[i]>1:\n",
    "                            len_common=oldList[i]\n",
    "                            strDict[len_common] = str2[i+1-len_common:i+1]\n",
    "                    # 边缘情况：处理矩阵每行第一个元素：直接更新currList[i]为1\n",
    "                    if i==0:\n",
    "                        currList[i]=1\n",
    "                    else:\n",
    "                        currList[i]=oldList[max(0,i-1)]+1\n",
    "\n",
    "\n",
    "                else:\n",
    "                    # 策略：只有s2!=s1且上一行左上值大于1时（即对角线断了）的场景才保存一次strDict\n",
    "                    # 但是这样无法处理最后一个值s1==s2的情况，因为该情况不更新strDict。故需要在最后一行一列的位置额外处理currList。\n",
    "                    currList[i]=0\n",
    "                    if i>1 and oldList[i-1]>1:\n",
    "                        len_common = oldList[i-1]\n",
    "                        strDict[len_common] = str2[i-len_common:i]\n",
    "\n",
    "                        # 边缘情况： 处理每行最后一个元素\n",
    "                    if i==len2-1 and oldList[i]>1:\n",
    "                        len_common = oldList[i]\n",
    "                        strDict[len_common] = str2[i-len_common+1:]\n",
    "                # 边缘情况：处理矩阵最后一行: 直接用currList，不再使用oldList判断是否停止\n",
    "                if r == len1-2:\n",
    "                    #pdb.set_trace()\n",
    "                    if currList[i]>1:\n",
    "                        len_common = currList[i]\n",
    "                        strDict[len_common] = str2[i+1-len_common:i+1]\n",
    "        strDict = {k:v for k,v in strDict.items() if v==v[::-1]}\n",
    "        if len(strDict)==0:\n",
    "            return str1[0]\n",
    "        else:\n",
    "            return strDict[max(strDict.keys())]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        start = 0\n",
    "        end = 1\n",
    "        if len(s) == 0: return ''\n",
    "\n",
    "        for i in range(len(s) - 1):\n",
    "            len1 = self.pointexpand(s, i, i)\n",
    "            len2 = self.pointexpand(s, i, i + 1)\n",
    "            max_len = max(len1, len2)\n",
    "            if max_len > end - start:\n",
    "                start = i - (max_len - 1)//2\n",
    "                end = start + max_len\n",
    "            print(i, start, max_len)\n",
    "        return s[start:end]\n",
    "\n",
    "    def pointexpand(self, s, l, r):\n",
    "        while l >= 0 and r < len(s) and s[l] == s[r]:\n",
    "            l -= 1\n",
    "            r += 1\n",
    "        return r - l - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not s:\n",
    "            return \"\"\n",
    "        if len(s)==1:\n",
    "            return s\n",
    "        l=[]\n",
    "        len1=len(s)\n",
    "        for index,i in enumerate(s):\n",
    "            for index_1,j in enumerate(s[:index:-1]):\n",
    "                s1=s[index:len1-index_1]\n",
    "                if s1==s1[::-1]:\n",
    "                    l.append(s1)\n",
    "                    break\n",
    "        d={}\n",
    "        if not l:\n",
    "            return s[-1]\n",
    "        for i in l:\n",
    "            d[i]=len(i)\n",
    "        return max(d, key=d.get)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: 'str') -> 'str':\n",
    "        # 动态规划解法\n",
    "        res = \"\"\n",
    "        lens = len(s)\n",
    "        if lens==0:\n",
    "            return res\n",
    "\n",
    "        \n",
    "        indexlist = [(i,i) for i in range(lens)]\n",
    "        indexlist_lens = [1] * lens\n",
    "        indexlist_even = [(i,i) for i in range(lens)]\n",
    "        indexlist_lens_even = [1] * lens\n",
    "        \n",
    "        for ind in range(lens):\n",
    "            left, right = indexlist[ind]\n",
    "            while(True):\n",
    "                _left = left - 1\n",
    "                _right = right + 1\n",
    "                if _left >= 0 and _right < lens and s[_left] == s[_right]:\n",
    "                    indexlist[ind] = (_left, _right)\n",
    "                    indexlist_lens[ind] = _right - _left + 1\n",
    "                    left, right = _left, _right\n",
    "                else:\n",
    "                    break\n",
    "                        \n",
    "            left, right = indexlist_even[ind]\n",
    "            if right + 1 < lens and s[left] == s[right + 1]:\n",
    "                right += 1\n",
    "                indexlist_even[ind] = (left, right)\n",
    "                indexlist_lens_even[ind] = right - left + 1\n",
    "                while(True):\n",
    "                    _left = left - 1\n",
    "                    _right = right + 1\n",
    "                    if _left >= 0 and _right < lens and s[_left] == s[_right]:\n",
    "                        indexlist_even[ind] = (_left, _right)\n",
    "                        indexlist_lens_even[ind] = _right - _left + 1\n",
    "                        left, right = _left, _right\n",
    "                    else:\n",
    "                        break\n",
    "                            \n",
    "        max1, max2 = max(indexlist_lens), max(indexlist_lens_even)\n",
    "        if max1 >= max2:\n",
    "            left, right = indexlist[indexlist_lens.index(max1)]\n",
    "            if left != right:\n",
    "                res = s[left:right + 1]\n",
    "            else:\n",
    "                res = s[left]           \n",
    "        else:\n",
    "            left, right = indexlist_even[indexlist_lens_even.index(max2)]\n",
    "            res = s[left:right + 1]\n",
    "\n",
    "        return res\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if len(s) <= 1:\n",
    "            return s\n",
    "        tempChar = s[0:1]\n",
    "        maxLongS = tempChar\n",
    "        bufferArr = [maxLongS]\n",
    "        unBufferArr = []\n",
    "        flag = True\n",
    "        for index in range(1,len(s)):\n",
    "            tempS = s[index:index+1]\n",
    "            if tempChar != tempS:\n",
    "                flag = False\n",
    "                break\n",
    "            else:\n",
    "                maxLongS += tempS\n",
    "                bufferArr.append(maxLongS)\n",
    "        if flag:\n",
    "            return s\n",
    "        def judgeIsPal(s):\n",
    "            if len(s) >= 2:\n",
    "                if len(s) == 2:\n",
    "                    return s[0:1] == s[1:2]\n",
    "                else:\n",
    "                    l = len(s)\n",
    "                    midS = s[1:l-1]\n",
    "                    if midS in bufferArr:\n",
    "                        return s[0:1] == s[l-1:l]\n",
    "                    elif midS in unBufferArr:\n",
    "                        return False\n",
    "                    else:\n",
    "                        for index in range(len(s)//2):\n",
    "                            if s[index:index+1] != s[len(s)-1-index:len(s)-index]:\n",
    "                                return False\n",
    "                        return True\n",
    "            else:\n",
    "                return True\n",
    "        index = 0\n",
    "        for index in range(2*len(s)-1):\n",
    "            tempS = \"\"\n",
    "            start = 0\n",
    "            end = 0\n",
    "            if index % 2 == 0:  # 当前中心为某一个字符\n",
    "                start = index//2\n",
    "                end = index//2+1\n",
    "            else:  # 当前中心在字符中间位置\n",
    "                start = index//2\n",
    "                end = index//2+2\n",
    "            # print(\"index:%d start:%d end:%d \" % (index, start, end))\n",
    "            while start >= 0 and end <= len(s):\n",
    "                tempS = s[start:end]\n",
    "                # print(tempS, start, end)\n",
    "                if tempS in unBufferArr:\n",
    "                    break\n",
    "                if tempS in bufferArr:\n",
    "                    start -= 1\n",
    "                    end += 1\n",
    "                    continue\n",
    "                flag = judgeIsPal(tempS)\n",
    "                if flag:\n",
    "                    bufferArr.append(tempS)\n",
    "                    maxLongS = tempS if len(tempS) >= len(maxLongS) else maxLongS\n",
    "                    start -= 1\n",
    "                    end += 1\n",
    "                    if len(maxLongS) == len(s):\n",
    "                        return maxLongS\n",
    "                else:\n",
    "                    unBufferArr.append(tempS)\n",
    "                    break\n",
    "        return maxLongS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: 'str') -> 'str':\n",
    "        def find(l,r):\n",
    "            while l>=0 and r<len(s) and s[l]==s[r]:\n",
    "                l -= 1\n",
    "                r += 1\n",
    "            return s[l+1:r]\n",
    "            \n",
    "        ans = ''\n",
    "        for i in range(len(s)):\n",
    "            tmp = find(i,i)\n",
    "            if len(tmp) > len(ans):\n",
    "                ans = tmp\n",
    "            tmp = find(i,i+1)\n",
    "            if len(tmp) > len(ans):\n",
    "                ans = tmp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        # s.split()\n",
    "        # r = []\n",
    "        # count = {}\n",
    "        # for i in s:\n",
    "        #     if i not in r:\n",
    "        #         r.append(i)\n",
    "        #         count['i'] = 1\n",
    "        #     else:\n",
    "        #         count['i'] = 2\n",
    "        # if count['i'] == 2:\n",
    "        #     print()\n",
    "        '''\n",
    "        if s==s[::-1]:\n",
    "            return s\n",
    "        max_len = 1\n",
    "        res = s[0]\n",
    "        for i in range(len(s) - 1):\n",
    "            for j in range(i + 1, len(s)):\n",
    "                if j - i + 1 > max_len and s[i:j+1] == s[i:j+1][::-1]:\n",
    "                    max_len = j - i + 1\n",
    "                    res = s[i:j + 1]\n",
    "        return res\n",
    "        '''\n",
    "        # n = 0\n",
    "        # res =''\n",
    "        # for i in range(len(s)):\n",
    "        #     if s[i-n:i+1] == s[i-n:i+1][::-1]:\n",
    "        #         n += 1\n",
    "        #         res = s[i-n:i+1]\n",
    "        # return res\n",
    "\n",
    "       \n",
    "        if s == s[::-1]:\n",
    "            return s\n",
    "\n",
    "        max_str = s[0]\n",
    "        longest_length  = 1\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i+1, len(s)):\n",
    "                if s[i:j+1] == s[i:j+1][::-1] and j + 1 - i > longest_length:\n",
    "                    max_str = s[i:j+1]\n",
    "                    longest_length = j-i+1\n",
    "\n",
    "        return max_str"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def Pailindrome(self, s):\n",
    "        l = len(s)\n",
    "        i = 0\n",
    "        j = l-1\n",
    "        while i < j and s[i] == s[j]:\n",
    "            i += 1\n",
    "            j -= 1\n",
    "\n",
    "        if i >= j:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def tail_with_longestPailindrome(self, s, last_start_tail, last_end_tail):\n",
    "        for i in range(last_start_tail-1, last_end_tail):\n",
    "            if i < 0:\n",
    "                continue\n",
    "            if s[i] == s[last_end_tail]:\n",
    "                if self.Pailindrome(s[i+1: last_end_tail]):\n",
    "                    return i\n",
    "        return last_end_tail\n",
    "\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        start = 0\n",
    "        end = 0\n",
    "\n",
    "        start_tail = 0\n",
    "\n",
    "        l = len(s)\n",
    "        for i in range(l):\n",
    "            # [start_tail, i+1)\n",
    "            start_tail = self.tail_with_longestPailindrome(s, start_tail, i)\n",
    "            if end - start > i+1 - start_tail:\n",
    "                continue\n",
    "            else:\n",
    "                start = start_tail\n",
    "                end = i + 1\n",
    "\n",
    "        return s[start: end]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        maxl = 0\n",
    "        res = ''\n",
    "        for i in range(len(s)):\n",
    "            left, right = i, i\n",
    "            while(left >= 0 and right < len(s) and s[left] == s[right]):\n",
    "                if maxl < right - left + 1:\n",
    "                    maxl = right - left + 1\n",
    "                    res = s[left:right + 1]\n",
    "                left -= 1\n",
    "                right += 1\n",
    "            left, right = i, i + 1\n",
    "            while(left >= 0 and right < len(s) and s[left] == s[right]):\n",
    "                if maxl < right - left + 1:\n",
    "                    maxl = right - left + 1\n",
    "                    res = s[left:right + 1]\n",
    "                left -= 1\n",
    "                right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kuosan(self,s,left,right):\n",
    "        while left>=0 and right<=len(s)-1:\n",
    "            if s[left]==s[right]:\n",
    "                left-=1;\n",
    "                right+=1;\n",
    "            else:\n",
    "                break;\n",
    "        if left==right:\n",
    "            return s[left];\n",
    "        elif right-left==1:\n",
    "            return s[left];\n",
    "        else: \n",
    "            return s[left+1:right];\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        if not s:return '';\n",
    "        maxc=''\n",
    "        for i in range(len(s)):\n",
    "            s1=self.kuosan(s,i,i);\n",
    "            s2=self.kuosan(s,i,i+1);\n",
    "            if len(s2)>=len(s1):\n",
    "                if len(s2)>=len(maxc):\n",
    "                    maxc=s2;\n",
    "            else:\n",
    "                if len(s1)>=len(maxc):\n",
    "                    maxc=s1;\n",
    "        return maxc;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        if not s: return \"\"\n",
    "        length = len(s)\n",
    "        if length == 1 or s == s[::-1]: return s\n",
    "        max_len,start = 1,0\n",
    "        for i in range(1, length):\n",
    "            even = s[i-max_len:i+1]\n",
    "            odd = s[i-max_len-1:i+1]\n",
    "            if i - max_len - 1 >= 0 and odd == odd[::-1]:\n",
    "                start = i - max_len - 1\n",
    "                max_len += 2\n",
    "                continue\n",
    "            if i - max_len >= 0 and even == even[::-1]:\n",
    "                start = i - max_len\n",
    "                max_len += 1\n",
    "                continue\n",
    "        return s[start:start + max_len]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.max_len = 0\n",
    "        self.max_index = []\n",
    "\n",
    "    def get_center_list(self, s):\n",
    "        n = len(s)\n",
    "        single = []\n",
    "        double = []\n",
    "        center_index_list = []\n",
    "        if s[0] == s[1]:\n",
    "            center_index_list.append(([0, 1], 2))\n",
    "            double = [0, 1]\n",
    "\n",
    "        if s[n - 1] == s[n - 2]:\n",
    "            center_index_list.append(([n - 2, n - 1], 2))\n",
    "            double = [n - 2, n - 1]\n",
    "\n",
    "        for i in range(1, n - 1):\n",
    "            # 回文中心是双数\n",
    "            if s[i] == s[i + 1]:\n",
    "                center_index_list.append(([i, i + 1], 2))\n",
    "                double = [i, i + 1]\n",
    "\n",
    "            # 回文中心是单数\n",
    "            if s[i - 1] == s[i + 1]:\n",
    "                center_index_list.append(([i], 1))\n",
    "                single = [i]\n",
    "\n",
    "        self.max_len = 1\n",
    "        self.max_index = single\n",
    "        if double:\n",
    "            self.max_len = 2\n",
    "            self.max_index = double\n",
    "        return center_index_list\n",
    "\n",
    "    def get_max_index(self, curr_len, curr_start, curr_end):\n",
    "        if self.max_len < curr_len:\n",
    "            self.max_len = curr_len\n",
    "            self.max_index = [curr_start, curr_end]\n",
    "\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        if not s:\n",
    "            return \"\"\n",
    "\n",
    "        n = len(s)\n",
    "        if n <= 1:\n",
    "            return s\n",
    "\n",
    "        # 先找到最短回文的中心\n",
    "        max_len = 0\n",
    "        max_index = []\n",
    "        cid_list = self.get_center_list(s)\n",
    "        for (index_list, cnt) in cid_list:\n",
    "            curr_len = cnt\n",
    "            start, end = index_list[0], index_list[-1]\n",
    "            cycle_len = min(start, n - end - 1)\n",
    "            is_all_equal = True\n",
    "            for i in range(1, cycle_len + 1):\n",
    "                curr_start = start - i\n",
    "                curr_end = end + i\n",
    "                if s[curr_start] == s[curr_end]:\n",
    "                    curr_len += 2\n",
    "                else:\n",
    "                    is_all_equal = False\n",
    "                    self.get_max_index(curr_len, curr_start + 1, curr_end - 1)\n",
    "                    break\n",
    "\n",
    "            if is_all_equal:\n",
    "                self.get_max_index(curr_len, start - cycle_len, end + cycle_len)\n",
    "\n",
    "        if not self.max_index:\n",
    "            return s[0]\n",
    "\n",
    "        max_s = s[self.max_index[0]: self.max_index[-1] + 1]\n",
    "        return max_s\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.max_len = 0\n",
    "        self.max_index = []\n",
    "\n",
    "    def get_center_list(self, s):\n",
    "        n = len(s)\n",
    "        single = []\n",
    "        double = []\n",
    "        center_index_list = []\n",
    "        if s[0] == s[1]:\n",
    "            center_index_list.append(([0, 1], 2))\n",
    "            double = [0, 1]\n",
    "\n",
    "        if s[n - 1] == s[n - 2]:\n",
    "            center_index_list.append(([n - 2, n - 1], 2))\n",
    "            double = [n - 2, n - 1]\n",
    "\n",
    "        for i in range(1, n - 1):\n",
    "            # 回文中心是双数\n",
    "            if s[i] == s[i + 1]:\n",
    "                center_index_list.append(([i, i + 1], 2))\n",
    "                double = [i, i + 1]\n",
    "\n",
    "            # 回文中心是单数\n",
    "            if s[i - 1] == s[i + 1]:\n",
    "                center_index_list.append(([i], 1))\n",
    "                single = [i]\n",
    "\n",
    "        self.max_len = 1\n",
    "        self.max_index = single\n",
    "        if double:\n",
    "            self.max_len = 2\n",
    "            self.max_index = double\n",
    "        return center_index_list\n",
    "\n",
    "    def get_max_index(self, curr_len, curr_start, curr_end):\n",
    "        if self.max_len < curr_len:\n",
    "            self.max_len = curr_len\n",
    "            self.max_index = [curr_start, curr_end]\n",
    "\n",
    "        #print(\"## 111 ### \", curr_len, self.max_len, curr_start, curr_end)\n",
    "\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        #s_list = [\"a\" for i in range(1000)]\n",
    "        #s = \"\".join(s_list)\n",
    "        if not s:\n",
    "            return \"\"\n",
    "\n",
    "        n = len(s)\n",
    "        if n <= 1:\n",
    "            return s\n",
    "\n",
    "        # 先找到最短回文的中心\n",
    "        max_len = 0\n",
    "        max_index = []\n",
    "        cid_list = self.get_center_list(s)\n",
    "        print(\"cid_list =\", cid_list)\n",
    "        for (index_list, cnt) in cid_list:\n",
    "            #print(\"-----------------------------------\")\n",
    "            curr_len = cnt\n",
    "            start, end = index_list[0], index_list[-1]\n",
    "            #print(\"start = %d, end = %d\" % (start, end))\n",
    "            cycle_len = min(start, n - end - 1)\n",
    "            #print(\"cycle_len = %d\" % (cycle_len))\n",
    "            is_all_equal = True\n",
    "            for i in range(1, cycle_len + 1):\n",
    "                curr_start = start - i\n",
    "                curr_end = end + i\n",
    "                #print(\"curr_start = %d, curr_end = %d\" % (curr_start, curr_end))\n",
    "                #print(\"##### \", s[curr_start], s[curr_end])\n",
    "                if s[curr_start] == s[curr_end]:\n",
    "                    curr_len += 2\n",
    "                else:\n",
    "                    #print(11111111111111)\n",
    "                    is_all_equal = False\n",
    "                    self.get_max_index(curr_len, curr_start + 1, curr_end - 1)\n",
    "                    break\n",
    "\n",
    "            if is_all_equal:\n",
    "                self.get_max_index(curr_len, start - cycle_len, end + cycle_len)\n",
    "\n",
    "        #print(\"self.max_index =\", self.max_index)\n",
    "        if not self.max_index:\n",
    "            return s[0]\n",
    "\n",
    "        max_s = s[self.max_index[0]: self.max_index[-1] + 1]\n",
    "        #print(\"max_s =\", max_s)\n",
    "        #if s == max_s:\n",
    "        #    print(\"================================\")\n",
    "        return max_s\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "\n",
    "        Len=0\n",
    "        myStr=''\n",
    "        for i in range(len(s)):\n",
    "            myList=[]\n",
    "            for j in range(i,len(s)):\n",
    "                myList.append(s[j])\n",
    "                if myList[0]==myList[-1] and len(myList)>Len and myList==list(reversed(myList)):\n",
    "                    #首尾相同                  #长度判断                    #翻转前后相同\n",
    "                    Len=len(myList)\n",
    "                    myStr=s[i:j+1]\n",
    "                \n",
    "        # print(Len)\n",
    "        # print(myStr)\n",
    "\n",
    "        return myStr\n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, st: str) -> str:\n",
    "            n = len(st)\n",
    "            if n==0:\n",
    "                return\n",
    "            \n",
    "            s,t = 0,0\n",
    "            \n",
    "            i = 0\n",
    "            while i<n:\n",
    "                r =l = i\n",
    "                while r<n-1 and st[l]==st[r+1]: r+=1\n",
    "                i = r+1\n",
    "                while l>0 and r < n-1 and st[l-1]==st[r+1]:\n",
    "                    r+=1\n",
    "                    l-=1\n",
    "                if r-l>t-s:\n",
    "                    s = l\n",
    "                    t = r\n",
    "                \n",
    "\n",
    "            return st[s:t+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        ans = \"\"\n",
    "        def isaba(text):\n",
    "            # 判断一个数是不是回文\n",
    "            return text == text[::-1]\n",
    "\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i + 1,len(s) + 1):\n",
    "                temp = s[i:j]\n",
    "                if isaba(temp) and len(ans) < len(temp):\n",
    "                    ans = temp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        # if len(s) < 2 or s == s[::-1]:\n",
    "        #     return s\n",
    "        # target_str = ''\n",
    "        # for i in range(len(s)):\n",
    "        #     for j in range(i, len(s)):\n",
    "        #         if s[i:j+1] == s[i:j+1][::-1] and len(s[i:j+1]) >= len(target_str):\n",
    "        #             target_str = s[i:j+1]\n",
    "        # return target_str\n",
    "        if len(s) < 2 or s == s[::-1]:\n",
    "            return s\n",
    "        res = s[0]\n",
    "        maxlen = 1\n",
    "        for i in range(1, len(s)):\n",
    "            odd = s[i - maxlen - 1: i + 1]\n",
    "            even = s[i - maxlen: i + 1]\n",
    "            if even == even[::-1] and i - maxlen >= 0:\n",
    "                res = even\n",
    "                maxlen += 1\n",
    "                continue\n",
    "            if odd == odd[::-1] and i - maxlen - 1 >= 0:\n",
    "                res = odd\n",
    "                maxlen += 2\n",
    "                continue\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        res = ''\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i+1,len(s)+1):\n",
    "                tmp = s[i:j]\n",
    "                if tmp == tmp[::-1] and len(tmp) > len(res):\n",
    "                    res =tmp\n",
    "                \n",
    "            \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:     \n",
    "        n = len(s)\n",
    "        ans = s[0]\n",
    "        if n == 1:\n",
    "            return ans\n",
    "        for i in range(n-1):\n",
    "            for j  in range(i+1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    res = s[i:j+1]\n",
    "                    if res == res[::-1] and len(res) > len(ans):\n",
    "                        ans = res                 \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        \n",
    "        def checkstring(str1):\n",
    "            l, r = 0, len(str1)-1\n",
    "            while l <= r:\n",
    "                if str1[l] != str1[r]:\n",
    "                    return(False)\n",
    "                l = l+1; r = r-1\n",
    "            return(True)\n",
    "\n",
    "        for i in range(len(s), 1, -1):\n",
    "            l = 0\n",
    "            r = i \n",
    "            for delta in range(0, len(s)-i+1):\n",
    "                if checkstring(s[l+delta:r+delta]):\n",
    "                    return(s[l+delta:r+delta])\n",
    "        return(s[0])\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s, left, right):\n",
    "        # print(left, right)\n",
    "        while left >= 0 and right < len(s) and s[left] == s[right]:\n",
    "            left -= 1\n",
    "            right += 1\n",
    "        return (right - left - 2) // 2\n",
    "\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        start, end = 0, 0   # 记录下最长字符串的起始位置\n",
    "        center, right = 0, 0\n",
    "        s = '#' + '#'.join(list(s)) + '#'   # 处理一下字符串，统一奇偶\n",
    "        arm_len = []    # 存储对应位置的回文臂长\n",
    "\n",
    "        for i in range(len(s)):\n",
    "\n",
    "            j = center\n",
    "            n = 0\n",
    "            while j < i:\n",
    "                n += 1\n",
    "                if j + arm_len[j] > right:\n",
    "                    center = j\n",
    "                    right = center + arm_len[center]\n",
    "                j += 1\n",
    "            print(center, right, n)\n",
    "            if center != i and center + arm_len[center] > i:\n",
    "                i_sym = 2 * center - i\n",
    "                min_arm_len = min(center + arm_len[center] - i, arm_len[i_sym])\n",
    "                curr_arm_len = self.expand(s, i - min_arm_len, i + min_arm_len)\n",
    "            else:\n",
    "                center = i\n",
    "                curr_arm_len = self.expand(s, i, i)\n",
    "                right = center + 2 * curr_arm_len + 1\n",
    "            \n",
    "            arm_len.append(curr_arm_len)\n",
    "\n",
    "            if 2 * curr_arm_len + 1 > end - start:\n",
    "                end = i + curr_arm_len\n",
    "                start = i - curr_arm_len\n",
    "\n",
    "        return s[start+1:end:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        n=len(s)\n",
    "        dict={}\n",
    "        for i in range(n):\n",
    "            j=0\n",
    "            while i-j>=0 and i+j<n:\n",
    "                if s[i-j]==s[i+j]:\n",
    "                    dict.setdefault(2*j+1,s[i-j:i+j+1])\n",
    "                    j+=1\n",
    "                else: break\n",
    "            j=1\n",
    "            while i-j+1>=0 and i+j<n:\n",
    "                if s[i-j+1]==s[i+j]:\n",
    "                    dict.setdefault(2*j,s[i-j+1:i+j+1])\n",
    "                    j+=1\n",
    "                else: break\n",
    "        return dict[max(dict)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        for i in range(len(s),0,-1):\n",
    "            fin_s = []\n",
    "            startIndex = 0\n",
    "            while True:\n",
    "                fin_s.append(s[startIndex:startIndex + i])\n",
    "                startIndex = startIndex + 1\n",
    "                if startIndex + i > len(s):\n",
    "                    break\n",
    "            for subString in fin_s:\n",
    "                if subString[::-1] == subString:\n",
    "                    return subString\n",
    "\n",
    "    \n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "\n",
    "        def is_palindrome(string):\n",
    "            return string[::] == string[::-1]\n",
    "        \n",
    "        s_length = len(s)\n",
    "        result = []\n",
    "        # 对每一行开始循环,代表一个中心扩散点\n",
    "        for line_index in range(s_length):\n",
    "            # 先判断这一个点的情况，再判断两个点的情况\n",
    "            # 一个点\n",
    "            # 初始化左右指针\n",
    "            left = line_index - 1\n",
    "            right = line_index + 1\n",
    "            # 退出判断循环的条件是，左右指针越界或者左右指针不相等\n",
    "            while left >= 0 and right <= s_length - 1:\n",
    "                if s[left] == s[right]:\n",
    "                    left -= 1\n",
    "                    right += 1\n",
    "                    continue\n",
    "                else:\n",
    "                    break\n",
    "            result.append((s[left+1:right],right-left-1))\n",
    "            # 两个点\n",
    "            if line_index != s_length-1:\n",
    "                if s[line_index] == s[line_index+1]:\n",
    "                    left = line_index - 1\n",
    "                    right = line_index + 2\n",
    "                    while left >= 0 and right <= s_length - 1:\n",
    "                        if s[left] == s[right]:\n",
    "                            left -= 1\n",
    "                            right += 1\n",
    "                            continue\n",
    "                        else:\n",
    "                            break\n",
    "                    result.append((s[left+1:right],right-left-1))\n",
    "        max_length = 0\n",
    "        max_length_string = ''\n",
    "        for res in result:\n",
    "            if res[1] > max_length:\n",
    "                max_length = res[1]\n",
    "                max_length_string = res[0]\n",
    "        return max_length_string\n",
    "                \n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, string: str) -> str:\n",
    "        length = len(string)\n",
    "        commons = []\n",
    "        for i in range(length):\n",
    "            if i + 1 < length and string[i] == string[i+1]:\n",
    "                common = string[i:i+2]\n",
    "                if i > 0:\n",
    "                    j = 1\n",
    "                    while (i - j) >= 0 and (i + 1 + j) < length:\n",
    "                        if string[i-j] == string[i+1+j]:\n",
    "                            common = string[i-j] + common + string[i+1+j]\n",
    "                        else:\n",
    "                            break\n",
    "                        j += 1\n",
    "                commons.append(common)\n",
    "\n",
    "            if i + 2 < length and string[i] == string[i+2]:\n",
    "                common = string[i:i+3]\n",
    "                j = 1\n",
    "                while (i - j) >= 0 and (i + 2 + j) < length:\n",
    "                    if string[i-j] == string[i+2+j]:\n",
    "                        common = string[i-j] + common + string[i+2+j]\n",
    "                    else:\n",
    "                        commons.append(common)\n",
    "                        break\n",
    "                    j += 1\n",
    "                commons.append(common)\n",
    "\n",
    "        if len(commons) > 0:\n",
    "            commons = sorted(commons, key=len)\n",
    "            return commons[-1]\n",
    "        else:\n",
    "            return string[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "\n",
    "        memo = []\n",
    "\n",
    "        def extend(l, r):\n",
    "            while l >= 0 and r <= n-1 and s[l] == s[r]:\n",
    "                r = r + 1\n",
    "                l = l - 1\n",
    "            return l, r, s[l+1:r]\n",
    "\n",
    "        p = 1\n",
    "        while p < n:\n",
    "            if s[p-1] == s[p]:\n",
    "                l, r, res = extend(p-1, p)\n",
    "                memo.append(res)\n",
    "\n",
    "            if p+1 < n and s[p+1] == s[p]:\n",
    "                l, r, res = extend(p, p+1)\n",
    "                memo.append(res)\n",
    "\n",
    "            if p+1 < n and s[p-1] == s[p+1]:\n",
    "                l, r, res =extend(p-1, p+1)\n",
    "                memo.append(res)\n",
    "\n",
    "            p += 1\n",
    "\n",
    "        if memo:\n",
    "            ans = memo[0]\n",
    "            for i in range(1, len(memo)):\n",
    "                if len(memo[i]) > len(ans):\n",
    "                    ans = memo[i]\n",
    "            return ans\n",
    "        else:\n",
    "            return s[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        s =\"*\".join(s)\n",
    "        ans = list()\n",
    "        for i in range(0, len(s)):\n",
    "            l = i\n",
    "            r = i\n",
    "            while l - 1 >= 0 and r + 1 < len(s):\n",
    "                if s[l - 1] == s[r + 1]:\n",
    "                    l -= 1\n",
    "                    r += 1\n",
    "                else:\n",
    "                    break\n",
    "            ans.append(s[l: r+1])\n",
    "        res = \"\"\n",
    "        for j in range(len(ans)):\n",
    "            res = \"\".join(ans[j].split('*')) if len(\"\".join(ans[j].split('*'))) > len(res) else res\n",
    "        return res\n",
    "\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        reverse_s = s[::-1] # 反转字符串\n",
    "        lenth = len(s)\n",
    "        ans = []\n",
    "        for i in range(2*lenth-1):\n",
    "            tmp = \"\"\n",
    "            if i < lenth:\n",
    "                s1 = s[lenth-i-1:]\n",
    "                s2 = reverse_s[:i+1]\n",
    "                for x,y in list(zip(s1,s2)):\n",
    "                    if x==y:\n",
    "                        tmp += x\n",
    "                    else:\n",
    "                        if len(tmp) != 0:\n",
    "                            ans.append(tmp)\n",
    "                        tmp = \"\"\n",
    "                if len(tmp) != 0:\n",
    "                    ans.append(tmp)\n",
    "                # if s[lenth-i-1:] == reverse_s[:i+1]:\n",
    "                #     ans.append(reverse_s[:i+1])\n",
    "            else:\n",
    "                s1 = s[:2 * lenth - i - 1]\n",
    "                s2 = reverse_s[i - lenth + 1:]\n",
    "                for x, y in list(zip(s1, s2)):\n",
    "                    if x == y:\n",
    "                        tmp += x\n",
    "                    else:\n",
    "                        if len(tmp) != 0:\n",
    "                            ans.append(tmp)\n",
    "                        tmp = \"\"\n",
    "                if len(tmp) != 0:\n",
    "                    ans.append(tmp)\n",
    "                # if s[:2*lenth - i-1] == reverse_s[i-lenth+1:]:\n",
    "                #     ans.append(s[:2*lenth - i-1])\n",
    "            # if len(tmp) != 0:\n",
    "            #     ans.append(tmp)\n",
    "        ans =list(set(ans))\n",
    "        ans.sort(key=lambda x:len(x), reverse=True)\n",
    "        answer = [x for x in ans if x == x[::-1]]\n",
    "        return answer[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        if n < 2: return s\n",
    "        \n",
    "        maxlen = 0\n",
    "        ansl = 0\n",
    "        ansr = 0\n",
    "        dp = [False for _ in range(int((1+n)*n/2) + 1)]\n",
    "        def at(i, j):\n",
    "            return int((i+1)*i/2 + j)\n",
    "        for i in range(n): dp[at(i, i)] = True\n",
    "\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if s[i] == s[j] and (i-j <= 1 or dp[at(i-1, j+1)]):\n",
    "                    dp[at(i,j)] = True\n",
    "                    if i-j+1 > maxlen:\n",
    "                        maxlen = i-j+1\n",
    "                        ansl = j\n",
    "                        ansr = i\n",
    "        return s[ansl:ansr+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        dp = [[False for j in range(n - i)] for i in range(n)]\n",
    "        for i in range(n - 1):\n",
    "            dp[i][0] = True\n",
    "            dp[i][1] = s[i] == s[i + 1]\n",
    "        dp[-1][0] = True\n",
    "        for j in range(2, n):\n",
    "            for i in range(n):\n",
    "                if i + j <= n - 1:\n",
    "                    dp[i][j] = dp[i + 1][j - 2] and s[i] == s[i + j]\n",
    "        for j in range(n - 1, -1, -1):\n",
    "            for i in range(n):\n",
    "                if j < len(dp[i]):\n",
    "                    if dp[i][j]:\n",
    "                        return s[i:i + j + 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        length = len(s)\n",
    "        if length==0:\n",
    "            return None\n",
    "        if length==1:\n",
    "            return s\n",
    "        list = []\n",
    "        resAns = ''\n",
    "        max = 0\n",
    "        for i in range(0,length):\n",
    "                l = i\n",
    "                r = i\n",
    "                while(l>=0 and r < length and s[l]==s[r]):\n",
    "                    l -= 1\n",
    "                    r += 1\n",
    "                tmp = s[l+1:r]\n",
    "                if len(tmp) > max:\n",
    "                    max = len(tmp)\n",
    "                    resAns = tmp\n",
    "                print('这里：' + tmp)\n",
    "                list.append(tmp)\n",
    "        for i in range(0,length):\n",
    "                l = i\n",
    "                r = i+1\n",
    "                while (l >= 0 and r < length and s[l] == s[r]):\n",
    "                    l -= 1\n",
    "                    r += 1\n",
    "                tmp2 = s[l+1:r]\n",
    "                if len(tmp2) > max:\n",
    "                    max = len(tmp2)\n",
    "                    resAns = tmp2\n",
    "                print('中间2:' + tmp2)\n",
    "                list.append(tmp2)\n",
    "        print(list)\n",
    "        print(resAns)\n",
    "        return resAns\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        dp = [[False for i in range(j+1)] for j in range(len(s))]\n",
    "        max_s = \"\"\n",
    "        for j in range(len(s)):\n",
    "            for i in range(j,-1,-1):\n",
    "                if i==j:\n",
    "                    dp[j][i] = True\n",
    "                elif i==j-1:\n",
    "                    dp[j][i] = s[i]==s[j]\n",
    "                else:\n",
    "                    dp[j][i] = dp[j-1][i+1] and s[j]==s[i]\n",
    "                if dp[j][i] and j-i+1 > len(max_s):\n",
    "                    max_s = s[i:j+1]\n",
    "        return max_s\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        #假定最大回文字符串宽度为2k\n",
    "        m = len(s)-1#末位索引\n",
    "        chances = {-0.5:[]}#最大可能k:索引中心线\n",
    "        for i in range(m+1):\n",
    "            chances[i/2] = []\n",
    "            chances[i/2].append(i/2)\n",
    "            chances[i/2].append(m-i/2)\n",
    "        max_k = m/2\n",
    "        while max_k > 0:\n",
    "            for i in chances[max_k]:\n",
    "                k = max_k\n",
    "                for K in range(int(2*k),0,-2):\n",
    "                    if s[int(i-K/2)] != s[int(i+K/2)]:\n",
    "                        chances[K/2-1].append(i)\n",
    "                        break\n",
    "                    elif K/2 <= 1:\n",
    "                        return s[int(i-max_k):int(i+max_k+1)]\n",
    "            max_k -= 0.5\n",
    "        return s[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        def huiwen(a_str)->bool:\n",
    "            if a_str == a_str[::-1]:    #回文\n",
    "                return True\n",
    "            return False\n",
    "        lst = []\n",
    "        for i in range(0,len(s)):#一个以上的字符\n",
    "            if len(s) == 1:\n",
    "                lst.append(s)\n",
    "            for j in range(len(s)-1,i,-1):\n",
    "                a = ''\n",
    "                if s[i] == s[j]:\n",
    "                    a = s[i:j+1]\n",
    "                    # print(a)\n",
    "                    if huiwen(a) :\n",
    "                        lst.append(a)\n",
    "                        # print(lst)\n",
    "                        break\n",
    "                else:\n",
    "                    a = s[j]\n",
    "                    lst.append(a)\n",
    "        dic = {k:len(k) for k in lst}\n",
    "        return (max(dic,key=dic.get))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        Len = len(s)\n",
    "        if Len==1:\n",
    "            return s\n",
    "\n",
    "        # 初始化 dp\n",
    "        dp = {}\n",
    "        for i in range(Len):\n",
    "            dp[i] = [True]\n",
    "        # 初始化最长序列\n",
    "        MAX = 1\n",
    "        S = s[0]\n",
    "        \n",
    "\n",
    "        for right in range(1,len(s)):\n",
    "            left = 0\n",
    "            while(right < Len):\n",
    "                # print(left, right)                \n",
    "\n",
    "                # 相邻或者不相邻且两端相同\n",
    "                if s[left]==s[right] and \\\n",
    "                (right-left==1 or dp[left+1][(right-1)-(left+1)]):      \n",
    "                    dp[left].append(True)\n",
    "                    if right-left+1 > MAX:\n",
    "                        MAX = right-left+1\n",
    "                        S = s[left:right+1]\n",
    "                else:\n",
    "                    dp[left].append(False)\n",
    "\n",
    "                left, right = left+1, right+1\n",
    "\n",
    "        return S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from array import array\n",
    "\n",
    "L_TYPE = ord('L')\n",
    "S_TYPE = ord('S')\n",
    "\n",
    "def is_lms(i, t):\n",
    "    \"\"\"Returns whether the suffix/ character at index i is a leftmost S-type\"\"\"\n",
    "    return t[i] == S_TYPE and t[i - 1] == L_TYPE\n",
    "\n",
    "\n",
    "def print_types(data: bytearray):\n",
    "    \"\"\"Simple method to the types of the characters of T\"\"\"\n",
    "    print(data.decode('ascii'))\n",
    "    print(\"\".join(\n",
    "        \"^\" if is_lms(i, data) else \" \"\n",
    "        for i in range(len(data))\n",
    "    ))\n",
    "\n",
    "\n",
    "def classify(text, n) -> bytearray:\n",
    "    \"\"\"Classifies the suffixes in text as either S-type, or L-type\n",
    "    This method can be merged with find_lms_suffixes but I have not done so for readability\n",
    "    Args:\n",
    "        text: the input string/array to be classified\n",
    "        n: the length of text\n",
    "    Returns:\n",
    "        t: a bytearray object, where t[i] contains the type of text[i]\n",
    "    \"\"\"\n",
    "    t = bytearray(n)\n",
    "    t[-1] = S_TYPE\n",
    "    for i in range(n - 2, -1, -1):\n",
    "        if text[i] == text[i + 1]:\n",
    "            t[i] = t[i + 1]\n",
    "        else:\n",
    "            if text[i] > text[i + 1]:\n",
    "                t[i] = L_TYPE\n",
    "            else:\n",
    "                t[i] = S_TYPE\n",
    "    return t\n",
    "\n",
    "\n",
    "def find_lms_suffixes(t, n):\n",
    "    \"\"\"Finds the positions of all lms_suffixes\n",
    "    Args:\n",
    "        t: the type array\n",
    "        n: the length of text and t\n",
    "    \"\"\"\n",
    "    pos = array('l')\n",
    "    for i in range(n):\n",
    "        if t[i] == S_TYPE and t[i - 1] == L_TYPE:\n",
    "            pos.append(i)\n",
    "    return pos\n",
    "\n",
    "\n",
    "def print_buckets(bucks):\n",
    "    \"\"\"Simple method to print bucket sizes\"\"\"\n",
    "    res = '[ '\n",
    "    for b in bucks:\n",
    "        if b != 0:\n",
    "            res += str(b)\n",
    "            res += ' '\n",
    "    res += ']'\n",
    "    print(res)\n",
    "\n",
    "\n",
    "def buckets(text, sigma):\n",
    "    \"\"\"Find the alphabet and the sizes of the bucket for each character in the text\"\"\"\n",
    "    alpha = []\n",
    "    bucket_sizes = array('L', [0] * sigma)\n",
    "    for c in text:\n",
    "        bucket_sizes[c] += 1\n",
    "    for i in range(sigma):\n",
    "        if bucket_sizes[i] != 0:\n",
    "            alpha.append(i)\n",
    "\n",
    "    # print_buckets(bucket_sizes)\n",
    "    return alpha, bucket_sizes\n",
    "\n",
    "\n",
    "def bucket_intervals(alpha, bucket_sizes, sigma):\n",
    "    \"\"\"Computes the bucket intervals, i.e heads and tails\"\"\"\n",
    "    heads = array('l', [0] * sigma)\n",
    "    tails = array('l', [0] * sigma)\n",
    "    j = 0\n",
    "    for i in range(len(alpha)):\n",
    "        heads[alpha[i]] = j\n",
    "        j += bucket_sizes[alpha[i]]\n",
    "        tails[alpha[i]] = j - 1\n",
    "\n",
    "    # print_buckets(heads)\n",
    "    # print_buckets(tails)\n",
    "    return heads, tails\n",
    "\n",
    "\n",
    "def induced_sorting(lms, tails, heads, SA, type_suffix, text, n, m, alpha, bucket_sizes, sigma):\n",
    "    \"\"\"Inductively creates the suffix array based on LMS\n",
    "    Args:\n",
    "        lms: an array indicating the positions of LMS Blocks/Suffixes in text\n",
    "        tails: an array indexed by the characters in T which tells the ends of the buckets\n",
    "        heads: an array indexed by the characters in T which tells the fronts of the buckets of those characters\n",
    "        SA: an empty array to be filled during the creation of the suffix array\n",
    "        type_suffix: an array in which type_suffix[i] tells the type of text[i]\n",
    "        text: the input whose suffix array is to be created\n",
    "        n: the length of the input 'text'\n",
    "        alpha: an array of the alphabet of T in sorted order\n",
    "        bucket_sizes: an array containing the sizes of each bucket: Used in resetting heads, tails\n",
    "        \"\"\"\n",
    "    for i in range(m-1, -1, -1):  # place LMS suffixes at the end of their buckets\n",
    "        nfs = tails[text[lms[i]]]\n",
    "        SA[nfs] = lms[i]\n",
    "        tails[text[lms[i]]] -= 1\n",
    "\n",
    "    for i in range(n):  # place the L-type suffixes at the fronts of their buckets\n",
    "        if SA[i] > 0 and type_suffix[SA[i] - 1] == L_TYPE:\n",
    "            nfs = heads[text[SA[i] - 1]]\n",
    "            SA[nfs] = SA[i] - 1\n",
    "            heads[text[SA[i] - 1]] += 1\n",
    "\n",
    "    # reset bucket counters\n",
    "    heads, tails = bucket_intervals(alpha, bucket_sizes, sigma)\n",
    "\n",
    "    for i in range(n-1, -1, -1):  # place the S-type suffixes at the ends of their buckets\n",
    "        if SA[i] > 0 and type_suffix[SA[i] - 1] == S_TYPE:\n",
    "            nfs = tails[text[SA[i] - 1]]\n",
    "            SA[nfs] = SA[i] - 1\n",
    "            tails[text[SA[i] - 1]] -= 1\n",
    "\n",
    "\n",
    "def blocks_are_equal(i, j, types, text, n):\n",
    "    \"\"\"Testing for the equality of two blocks\"\"\"\n",
    "    while i < n and j < n:\n",
    "        if text[i] == text[j]:\n",
    "            if is_lms(i, types) and is_lms(j, types):\n",
    "                return True\n",
    "            else:\n",
    "                i += 1\n",
    "                j += 1\n",
    "        else:\n",
    "            return False\n",
    "    return False\n",
    "\n",
    "\n",
    "def get_reduced_substring(types, SA, lms, ordered_lms, text, n, m):\n",
    "    \"\"\"Finds the reduced substring\"\"\"\n",
    "    j = 0\n",
    "    for i in range(n):\n",
    "        if is_lms(SA[i], types):\n",
    "            ordered_lms[j] = SA[i]\n",
    "            j += 1\n",
    "\n",
    "    # number the lms blocks and form the reduced substring\n",
    "    pIS = array('l', [0] * m)\n",
    "    k, i = 1, 1\n",
    "    pIS[0] = 0\n",
    "    for i in range(1, m):\n",
    "        if text[ordered_lms[i]] == text[ordered_lms[i - 1]] and \\\n",
    "                blocks_are_equal(ordered_lms[i] + 1, ordered_lms[i - 1] + 1, types, text, n):\n",
    "            pIS[i] = pIS[i - 1]\n",
    "        else:\n",
    "            pIS[i] = k\n",
    "            k += 1\n",
    "\n",
    "    # form the reduced substring\n",
    "\n",
    "    inverse_lms = array('l', [0] * n)\n",
    "    for i in range(m):\n",
    "        inverse_lms[ordered_lms[i]] = pIS[i]\n",
    "    for i in range(m):\n",
    "        pIS[i] = inverse_lms[lms[i]]\n",
    "\n",
    "    return pIS, k == m, k + 1\n",
    "\n",
    "\n",
    "def construct_suffix_array(T, SA, n, sigma):\n",
    "    \"\"\"Constructs the suffix array of T and stores it in SA\n",
    "    Args:\n",
    "        T: the text whose suffix array is to be built\n",
    "        SA: the array to be filled\n",
    "        n: the length of T and SA\n",
    "        sigma: the size of the alphabet of T, i.e the largest value in T\n",
    "        \"\"\"\n",
    "    if len(T) == 1:  # special case\n",
    "        SA[0] = 0\n",
    "        return SA\n",
    "\n",
    "    t = classify(T, n)  # step 1: classification\n",
    "    lms = find_lms_suffixes(t, n)  # step 2: finding the indices of LMS suffixes\n",
    "    m = len(lms)\n",
    "\n",
    "    # print_types(t)\n",
    "\n",
    "    alpha, sizes = buckets(T, sigma)  # finding the bucket sizes and alphabet of T\n",
    "    heads, tails = bucket_intervals(alpha, sizes, sigma)\n",
    "    induced_sorting(lms, tails, heads, SA, t, T, n, m, alpha, sizes, sigma)   # first induced sort\n",
    "\n",
    "    ordered_lms = array('L', [0] * len(lms))\n",
    "\n",
    "    reduced_text, blocks_unique, sigma_reduced = get_reduced_substring(t, SA, lms, ordered_lms, T, n, m)\n",
    "    reduced_SA = array('l', [-1] * m)  # reduced SA\n",
    "    if blocks_unique:  # base case\n",
    "        # compute suffix array manually\n",
    "        for i in range(m):\n",
    "            reduced_SA[reduced_text[i]] = i\n",
    "    else:\n",
    "        construct_suffix_array(reduced_text, reduced_SA, m, sigma_reduced)\n",
    "\n",
    "    # use the suffix array to sort the LMS suffixes\n",
    "    for i in range(m):\n",
    "        ordered_lms[i] = lms[reduced_SA[i]]\n",
    "\n",
    "    heads, tails = bucket_intervals(alpha, sizes, sigma)  # reset bucket tails and heads\n",
    "    for i in range(n):  SA[i] = 0  # clear suffix array\n",
    "    induced_sorting(ordered_lms, tails, heads, SA, t, T, n, m, alpha, sizes, sigma)\n",
    "\n",
    "\n",
    "def bwt(T, SA: array, BWT: bytearray, n: int):\n",
    "    \"\"\"If SA[i] = 0 then T[SA[i] - 1] = T[0 - 1] = T[-1] = '$\"\"\"\n",
    "    for i in range(n):\n",
    "        BWT[i] = T[SA[i] - 1]\n",
    "\n",
    "def isa(SA, ISA, n):\n",
    "    \"\"\"Constructs an inverse suffix array\"\"\"\n",
    "    for i in range(n):\n",
    "        ISA[SA[i]] = i\n",
    "\n",
    "\n",
    "def fm_index(SA, ISA, LF, n):\n",
    "    \"\"\"Constructs a last-to-first column mapping in linear time\"\"\"\n",
    "    for i in range(n):\n",
    "        if SA[i] == 0:\n",
    "            LF[i] = 0\n",
    "        else:\n",
    "            LF[i] = ISA[SA[i] - 1]\n",
    "\n",
    "\n",
    "def naive_suffix_array(s, n):\n",
    "    \"\"\"Naive suffix array implementation, just as a sanity check\"\"\"\n",
    "    sa_tuple = sorted([(s[i:], i) for i in range(n)])\n",
    "    return array('l', map(lambda x: x[1], sa_tuple))\n",
    "\n",
    "'''\n",
    "text: str:要处理的字符串\n",
    "return: sa \n",
    "'''\n",
    "def SAIS_sa(text):\n",
    "    text += '$'\n",
    "    text = [ord(c) for c in text]\n",
    "    sigma = max(text) + 1\n",
    "    n = len(text)\n",
    "    SA = array('l', [-1] * n)\n",
    "    construct_suffix_array(text, SA, n, sigma)\n",
    "    bt = bytearray(n)\n",
    "    bwt(text, SA, bt, n)\n",
    "    return SA.tolist()[1:]\n",
    "\n",
    "'''\n",
    "text: str:要处理的字符串\n",
    "return: sa,rk\n",
    "'''\n",
    "def SAIS_sa_rk(text):\n",
    "    sa = SAIS_sa(text)\n",
    "    rk = [0]*len(sa)\n",
    "    for i,sa_i in enumerate(sa):\n",
    "        rk[sa_i] = i\n",
    "    return sa,rk\n",
    "\n",
    "'''\n",
    "text: str:要处理的字符串\n",
    "return: sa,rk,h\n",
    "'''\n",
    "def SAIS_sa_rk_h(text):\n",
    "    sa = SAIS_sa(text)\n",
    "    n,k = len(sa),0\n",
    "    rk,h = [0]*n,[0]*n\n",
    "    for i,sa_i in enumerate(sa):\n",
    "        rk[sa_i] = i\n",
    "\n",
    "    for i in range(n):\n",
    "        if k>0: k-=1\n",
    "        while i+k<n and rk[i]-1>=0 and sa[rk[i]-1]+k<n and text[i+k]==text[sa[rk[i]-1]+k]:\n",
    "            k+=1\n",
    "        h[rk[i]] = k\n",
    "    return sa,rk,h\n",
    "\n",
    "\n",
    "\n",
    "class RMQ:\n",
    "    def __init__(self,a):\n",
    "        n=len(a)\n",
    "        maxn,maxs,maxb = len(a),len(a)+20,20\n",
    "        a = a+[0]*maxb # 扩充a\n",
    "\n",
    "        hightbit=[0]*maxs\n",
    "\n",
    "        stmax=[[0]*maxb for _ in range(maxs)]\n",
    "        premax=[[0]*maxb for _ in range(maxs)]\n",
    "        sufmax=[[0]*maxb for _ in range(maxs)]\n",
    "        quemax=[[0]*maxb for _ in range(maxs)]\n",
    "        stackmax = [0]*maxb\n",
    "\n",
    "        stmin=[[0]*maxb for _ in range(maxs)]\n",
    "        premin=[[0]*maxb for _ in range(maxs)]\n",
    "        sufmin=[[0]*maxb for _ in range(maxs)]\n",
    "        quemin=[[0]*maxb for _ in range(maxs)]\n",
    "        stackmin = [0]*maxb\n",
    "\n",
    "\n",
    "        B=int(math.log2(n))\n",
    "        S=(n-1)//B+1\n",
    "        for b in range(S):\n",
    "            stmin[b][0]=int(1e6)\n",
    "        for i in range(n):\n",
    "            stmin[i//B][0]=min(stmin[i//B][0],a[i])\n",
    "            stmax[i//B][0]=max(stmin[i//B][0],a[i])\n",
    "        for b in range(S-1,-1,-1):\n",
    "            k=1\n",
    "            while b+(1<<k)-1<S:\n",
    "                stmin[b][k] = min(stmin[b][k - 1], stmin[b + (1 << (k - 1))][k - 1])\n",
    "                stmax[b][k] = max(stmax[b][k - 1], stmax[b + (1 << (k - 1))][k - 1])\n",
    "                k+=1\n",
    "        for b in range(S):\n",
    "            be=b*B\n",
    "            premin[b][0],premax[b][0]=a[be],a[be]\n",
    "            for k in range(1,B):\n",
    "                premin[b][k] = min(premin[b][k - 1], a[be + k])\n",
    "                premax[b][k] = max(premax[b][k - 1], a[be + k])\n",
    "            sufmin[b][B-1],sufmax[b][B-1]=a[be+B-1],a[be+B-1]\n",
    "            for k in range(B-2,-1,-1):\n",
    "                sufmin[b][k] = min(sufmin[b][k + 1], a[be + k])\n",
    "                sufmax[b][k] = max(sufmax[b][k + 1], a[be + k])\n",
    "        for b in range(S):\n",
    "            be=b*B\n",
    "            spmin,nowmin,spmax,nowmax=0,0,0,0\n",
    "            for i in range(B):\n",
    "                while spmin and a[be + stackmin[spmin]] > a[be + i]:\n",
    "                    nowmin ^= 1 << stackmin[spmin]\n",
    "                    spmin-=1\n",
    "                while spmax and a[be + stackmax[spmax]] < a[be + i]:\n",
    "                    nowmax ^= 1 << stackmax[spmax]\n",
    "                    spmax-=1\n",
    "                spmin+=1\n",
    "                stackmin[spmin] = i\n",
    "                nowmin ^= 1<<i\n",
    "                quemin[b][i] = nowmin\n",
    "                spmax+=1\n",
    "                stackmax[spmax] = i\n",
    "                nowmax ^= 1<<i\n",
    "                quemax[b][i] = nowmax\n",
    "        for i in range(2,S+1):\n",
    "            hightbit[i] = hightbit[i>>1]+1\n",
    "\n",
    "        self.B = B\n",
    "        self.a = a\n",
    "        self.quemin = quemin\n",
    "        self.sufmin = sufmin\n",
    "        self.premin = premin\n",
    "        self.sufmax = sufmax\n",
    "        self.premax = premax\n",
    "        self.quemax = quemax\n",
    "        self.hightbit = hightbit\n",
    "        self.stmin = stmin\n",
    "        self.stmax = stmax\n",
    "\n",
    "    def transferLR(self,l,r,rk):\n",
    "        l,r = rk[l],rk[r]\n",
    "        if l>r: l,r=r,l\n",
    "        l+=1\n",
    "        return l,r\n",
    "\n",
    "    # 求[L,R]内的最值\n",
    "    def query_min_max(self,l,r,rk):\n",
    "        a = self.a\n",
    "        l,r = self.transferLR(l,r,rk)\n",
    "        L,R = l//self.B,r//self.B\n",
    "        li,ri = l%self.B,r%self.B\n",
    "        min_,max_ = 1e6,0\n",
    "\n",
    "        multiply_De_Bruijn_position = [\n",
    "            0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,\n",
    "            31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9]\n",
    "        def tail_zero_count(num):\n",
    "            return multiply_De_Bruijn_position[(((num & (-num)) * 0x077CB531) >> 27) & 31]\n",
    "\n",
    "        if L==R:\n",
    "            min_ = min(min_,a[l+tail_zero_count(self.quemin[R][ri] >> li)])\n",
    "            max_ = max(max_,a[l+tail_zero_count(self.quemax[R][ri] >> li)])\n",
    "        else:\n",
    "            min_ = min(min_,self.sufmin[L][li],self.premin[R][ri])\n",
    "            max_ = max(max_,self.sufmax[L][li],self.premax[R][ri])\n",
    "            len_ = R-L-1\n",
    "            k = self.hightbit[len_]\n",
    "            if len_>0:\n",
    "                min_ = min(min_,self.stmin[L+1][k],self.stmin[R-(1<<k)][k])\n",
    "                max_ = max(max_,self.stmax[L+1][k],self.stmax[R-(1<<k)][k])\n",
    "\n",
    "        return min_,max_\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, S: str) -> str:\n",
    "        S = S+'|'+S[::-1]\n",
    "        sa,rk,h = SAIS_sa_rk_h(S)\n",
    "        \n",
    "        R = RMQ(h)\n",
    "        \n",
    "        n = len(S)\n",
    "        s = 0 # 起始位置\n",
    "        l = 0 # 子串长度:较小的数\n",
    "        for i in range(n//2):\n",
    "            ht,_ = R.query_min_max(i,n-1-i,rk) # h数组值\n",
    "            lt = 2*ht-1 # 奇数 真实子串长度\n",
    "            if lt>l: s,l=i-ht+1,lt\n",
    "            if i!=0:\n",
    "                ht,_ = R.query_min_max(i,n-i,rk)\n",
    "                lt = 2*ht # 偶数\n",
    "                if lt>l: s,l=i-ht,lt\n",
    "\n",
    "        return S[s:s+l]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        #dp = [[0, 1]] * len(s)\n",
    "        # dp[i]: \n",
    "        dp = [[-1, 0] for _ in range(len(s))]\n",
    "        max_i = 0\n",
    "        max_j = 0\n",
    "        for j in range(1, len(s)):\n",
    "            for i in range(len(s) - j):\n",
    "                if s[i] == s[i + j] and (j - 2) in dp[i + 1]:\n",
    "                    dp[i].append(j)\n",
    "                    max_i = i\n",
    "                    max_j = j\n",
    "        return s[max_i:max_i+max_j+1]\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "# palindrome\n",
    "# j = 0: dp[i] = i\n",
    "# j = 1: if dp[i] == dp[i+1]: dp[i] = j\n",
    "# j = 2: if dp[i] == dp[i + j] && dp[i + 1] == j - 1: dp[i] = 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        result, length = [[1] for _ in range(len(s))], len(s)\n",
    "        for i in reversed(range(length - 1)):\n",
    "            if s[i] == s[i + 1]:\n",
    "                result[i][0] += result[i + 1][0]         \n",
    "            for j in result[i + 1]:\n",
    "                if i + 1 + j < length and s[i] == s[i + 1 + j]:\n",
    "                    result[i].append(j + 2)\n",
    "        index, l = max([(i, result[i]) for i in range(len(result))], key=lambda a: max(a[1]))\n",
    "        return s[index:index + max(l)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        def Palindrome(ss):\n",
    "            n = len(ss)\n",
    "            for i in range(int(n/2)):\n",
    "                if ss[i]!=ss[n-1-i]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        if s == []:\n",
    "            return []\n",
    "        elif len(s)==1:\n",
    "            return s\n",
    "        else:\n",
    "            l = len(s)\n",
    "            if l<=500:\n",
    "                sss = []\n",
    "                for i in range(400):\n",
    "                    for j in range(400):\n",
    "                        a=i*j\n",
    "                        sss.append(a)\n",
    "            i, j = 0, 1\n",
    "            output = \"\"\n",
    "            new_l = 0\n",
    "            for i in range(l-1):\n",
    "                for j in range(l-1, -1, -1):\n",
    "                    if j-i+1>new_l:\n",
    "                        new_s = s[i:j+1]\n",
    "                        if Palindrome(new_s)==True:\n",
    "                            output = new_s\n",
    "                            new_l = j-i+1\n",
    "                            if new_l>=l-i:\n",
    "                                return output\n",
    "            return output\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        if n < 2:\n",
    "            return s\n",
    "\n",
    "        max_len = 1\n",
    "        begin = 0\n",
    "        dp = [[False] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = True\n",
    "\n",
    "        for L in range(2, n + 1):\n",
    "            for i in range(n):\n",
    "                j = L + i - 1\n",
    "                if j >= n:\n",
    "                    break\n",
    "                if s[i] != s[j]:\n",
    "                    dp[i][j] = False\n",
    "                else:\n",
    "                    if j - i < 3:\n",
    "                        dp[i][j] = True\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i + 1][j - 1]\n",
    "\n",
    "                if dp[i][j] and j - i + 1 > max_len:\n",
    "                    max_len = j - i + 1\n",
    "                    begin = i \n",
    "        return s[begin: begin + max_len]        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        # n = len(s)\n",
    "        # if n < 2: \n",
    "        #     return s\n",
    "\n",
    "        # max_len = 1\n",
    "        # begin = 0\n",
    "        # # dp[i][j] 表示 s[i..j] 是否为回文串\n",
    "        # dp = [[False] * n for _ in range(n)]\n",
    "        # for i in range(n):\n",
    "        #     dp[i][i] = True\n",
    "        \n",
    "        # # 迭代开始\n",
    "        # # 先枚举字符串长度\n",
    "        # for L in range(2, n + 1):\n",
    "        #     # 枚举左边界，左边界的上限设置可以宽松一些\n",
    "        #     for i in range(n):\n",
    "        #         # 由 L 和 i 可以确定右边界，即 j - i + 1 = L \n",
    "        #         j = L + i - 1\n",
    "        #         # 如果右边界越界，就可以推出当前循环\n",
    "        #         if j >= n:\n",
    "        #             break\n",
    "                \n",
    "        #         if s[i] != s[j]:\n",
    "        #             dp[i][j] = False\n",
    "        #         else:\n",
    "        #             if j - i < 3:\n",
    "        #                 dp[i][j] = True\n",
    "        #             else:\n",
    "        #                 dp[i][j] = dp[i + 1][j - 1]\n",
    "                \n",
    "        #         # 只要 dp[i][L] == True 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置\n",
    "        #         if dp[i][j] and j - i + 1 > max_len:\n",
    "        #             max_len = j - i + 1\n",
    "        #             begin = i\n",
    "\n",
    "        # return s[begin: begin + max_len]\n",
    "\n",
    "\n",
    "# 该方法会超出时间限制\n",
    "# class Solution:\n",
    "#     def longestPalindrome(self, s: str) -> str:\n",
    "#         n = len(s)\n",
    "#         if n == 0:\n",
    "#             return ''\n",
    "#         if n == 1:\n",
    "#             return s\n",
    "        \n",
    "#         def check(l, r):  # 用于判断是否是回文串\n",
    "#             while l < r:\n",
    "#                 if s[l] == s[r]:\n",
    "#                     l += 1\n",
    "#                     r -= 1\n",
    "#                 else:\n",
    "#                     return False\n",
    "#             return True\n",
    "        \n",
    "#         m = []\n",
    "#         i = 0 \n",
    "#         while i < n - 1:\n",
    "#             for j in range(i + 1, n):\n",
    "#                 if s[i] == s[j] and check(i, j):  # 若找到一个回文字串\n",
    "#                     if j - i + 1 > len(m):  # 判断是否是最长的\n",
    "#                         m = s[i: j + 1]\n",
    "#             i += 1\n",
    "        \n",
    "#         return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        # l = len(s)\n",
    "        # dp = [[0 for i in range(l)] for j in range(l)]\n",
    "\n",
    "        # ans = s[0:1]\n",
    "\n",
    "        # for i in range(l):\n",
    "        #     dp[i][i] = 1\n",
    "\n",
    "        # for c in range(1, l):\n",
    "        #     for i in range(l-c):\n",
    "        #         if s[i] == s[i+c]:\n",
    "        #             if c <= 1:\n",
    "        #                 dp[i][i+c] = 1\n",
    "        #                 ans = s[i:i+c+1]\n",
    "        #             else:\n",
    "        #                 if dp[i+1][i+c-1] == 1:\n",
    "        #                     dp[i][i+c] = 1\n",
    "        #                     ans = s[i:i+c+1]\n",
    "        # return ans\n",
    "        n = len(s)\n",
    "        if n < 2:\n",
    "            return s\n",
    "        \n",
    "        max_len = 1\n",
    "        begin = 0\n",
    "        # dp[i][j] 表示 s[i..j] 是否是回文串\n",
    "        dp = [[False] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = True\n",
    "        \n",
    "        # 递推开始\n",
    "        # 先枚举子串长度\n",
    "        for L in range(2, n + 1):\n",
    "            # 枚举左边界，左边界的上限设置可以宽松一些\n",
    "            for i in range(n):\n",
    "                # 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得\n",
    "                j = L + i - 1\n",
    "                # 如果右边界越界，就可以退出当前循环\n",
    "                if j >= n:\n",
    "                    break\n",
    "                    \n",
    "                if s[i] != s[j]:\n",
    "                    dp[i][j] = False \n",
    "                else:\n",
    "                    if j - i < 3:\n",
    "                        dp[i][j] = True\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i + 1][j - 1]\n",
    "                \n",
    "                # 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置\n",
    "                if dp[i][j] and j - i + 1 > max_len:\n",
    "                    max_len = j - i + 1\n",
    "                    begin = i\n",
    "        return s[begin:begin + max_len]        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        if n < 2 or s==s[::-1]: return s  # 长度为1直接返回\n",
    "        start, maxLen = 0, 1  # 维护最长回文串的开始位置以及长度\n",
    "        f = [[False] * n for _ in range(n)]\n",
    "        for i in range(n): f[i][i] = True  # 长度为1的区间为回文串\n",
    "        for length in range(2, n + 1):  # 从2开始枚举区间长度\n",
    "            for l in range(n):  # 枚举区间左端点\n",
    "                r = l + length - 1\n",
    "                if r >= n: break  # 避免出现右端点越界的情况\n",
    "                if s[l] == s[r]:\n",
    "                    if f[l + 1][r - 1] or length == 2:  # 长度为2需要特判\n",
    "                        f[l][r] = True\n",
    "                        if length > maxLen:\n",
    "                            start, maxLen = l, length\n",
    "        return s[start:start + maxLen]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        if len(s)<2:return s\n",
    "        dp=[[False]*len(s) for _ in range(len(s))]\n",
    "        res=''\n",
    "        tmp=-1\n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            for j in range(i,len(s)):\n",
    "                if s[i]==s[j]:\n",
    "                    if j-i<=1:\n",
    "                        dp[i][j]=True\n",
    "                    else:\n",
    "                        dp[i][j]=dp[i+1][j-1]\n",
    "                if dp[i][j] and j-i>tmp:\n",
    "                    tmp=j-i\n",
    "                    res=s[i:j+1]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "\n",
    "        n = len(s)\n",
    "        if n < 2:\n",
    "            return s\n",
    "        \n",
    "        max_len = 1\n",
    "        begin = 0\n",
    "\n",
    "        # 初始化dp数组\n",
    "        # dp[i, j] 代表s[i:j]的子串是否是回文串\n",
    "        dp = [[False] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = True\n",
    "        \n",
    "        # for i in range(n):  \n",
    "        #     for sub_len in range(2, n + 1): 这样的循环嵌套会出错\n",
    "    \n",
    "        for sub_len in range(2, n + 1):\n",
    "            for i in range(n):  \n",
    "\n",
    "                j = sub_len + i - 1\n",
    "                if j >= n:\n",
    "                    break\n",
    "                \n",
    "                if s[i] != s[j]:\n",
    "                    dp[i][j] = False\n",
    "                else:\n",
    "                    dp[i][j] = True if j - i <= 2 else dp[i+1][j-1]\n",
    "                \n",
    "\n",
    "                if dp[i][j] and j - i + 1 > max_len:\n",
    "                    max_len = j - i + 1\n",
    "                    begin = i\n",
    "        \n",
    "        return s[begin: begin + max_len]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        if n < 2:\n",
    "            return s\n",
    "        \n",
    "        begin = 0\n",
    "        max_length = 1\n",
    "        dp = [[False] * n for _ in range(n)]\n",
    "        for L in range(2, n+1):\n",
    "            for i in range(n):\n",
    "                j = i + L - 1\n",
    "                if j >= n:\n",
    "                    break\n",
    "                \n",
    "                if s[i] != s[j]:\n",
    "                    dp[i][j] = False\n",
    "                else:\n",
    "                    if (j-1) - (i+1) + 1 < 2:\n",
    "                        dp[i][j] = True\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i+1][j-1]\n",
    "            \n",
    "                if dp[i][j] and L > max_length:\n",
    "                    max_length = L\n",
    "                    begin = i\n",
    "        \n",
    "\n",
    "        return s[begin:begin+max_length]\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "\n",
    "        if len(s) < 2:\n",
    "            return s\n",
    "        \n",
    "        dp = [[1]*len(s) for _ in range(len(s))]\n",
    "        begin = 0\n",
    "        max_len = 0\n",
    "\n",
    "\n",
    "        # right bd\n",
    "        for i in range(len(s)):\n",
    "            # left bd\n",
    "            for j in range(i+1):\n",
    "\n",
    "                if s[i] == s[j] and s[j:i+1] == s[j:i+1][::-1]:\n",
    "                    dp[j][i] = len(s[j:i+1])\n",
    "                    if max_len < len(s[j:i+1]):\n",
    "                        max_len = len(s[j:i+1])\n",
    "                        begin = j\n",
    "\n",
    "                    break\n",
    "\n",
    "        return s[begin:begin+max_len]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def expandAroundCenter(self, s, left, right):\n",
    "#         while left >= 0 and right < len(s) and s[left] == s[right]:\n",
    "#             left -= 1\n",
    "#             right += 1\n",
    "#         return left + 1, right - 1\n",
    "\n",
    "#     def longestPalindrome(self, s: str) -> str:\n",
    "#         start, end = 0, 0\n",
    "#         for i in range(len(s)):\n",
    "#             left1, right1 = self.expandAroundCenter(s, i, i)\n",
    "#             left2, right2 = self.expandAroundCenter(s, i, i + 1)\n",
    "#             if right1 - left1 > end - start:\n",
    "#                 start, end = left1, right1\n",
    "#             if right2 - left2 > end - start:\n",
    "#                 start, end = left2, right2\n",
    "#         return s[start: end + 1]\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def longestPalindrome(self, s: str) -> str:\n",
    "#         res=''\n",
    "#         for i in range(len(s)):\n",
    "#             odd_num = max(i-len(res), 0)\n",
    "#             tmp_odd = s[odd_num:i+1]\n",
    "#             even_num = max(i-len(res)-1, 0)\n",
    "#             tmp_even = s[even_num:i+1]\n",
    "#             if tmp_odd == tmp_odd[::-1]:\n",
    "#                 res = tmp_odd\n",
    "#             if tmp_even == tmp_even[::-1]:\n",
    "#                 res= tmp_even\n",
    "#         return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        dp = [[0 if i != j else 1 for i in range(n)] for j in range(n)]\n",
    "        max_sub_str = s[0]\n",
    "        max_length = 1\n",
    "        for L in range(2, n + 1):\n",
    "            for i in range(0, n):\n",
    "                j = i + L - 1\n",
    "                if j >= n:\n",
    "                    break\n",
    "                if s[i] == s[j] and (L == 2 or dp[i + 1][j - 1] == 1):\n",
    "                    dp[i][j] = 1\n",
    "                    if L > max_length:\n",
    "                        max_length = L\n",
    "                        max_sub_str = s[i:j+1]\n",
    "        return max_sub_str\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
